<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>



  
  
  <meta content="text/html;charset=ISO-8859-1" http-equiv="Content-Type">


  


  
  
  
  <title>Safe Ownership-Based Memory Management</title>
  <meta content="Adam Dingle" name="author">



  
  
  <style type="text/css">
h1 { font-size: 18pt;
font-weight: bold;
font-family: Arial,Helvetica,sans-serif;
text-align: center;
}
.author { font-family: Arial,Helvetica,sans-serif;
font-size: 12pt;
text-align: center;
}
address { text-align: center;
font-family: Arial,Helvetica,sans-serif;
font-size: 10pt;
font-style: normal;
}
body {
font-size: 9pt;
}
h2 { font-family: Times New Roman,Times,serif;
font-size: 12pt;
font-weight: bold;
}
h3 { font-family: Times New Roman,Times,serif;
font-size: 12pt;
font-weight: bold;
}
h4 { font-family: Times New Roman,Times,serif;
font-size: 11pt;
font-style: italic;
font-weight: normal;
}
  </style>
</head>


<body>

<h2>CONCLUSION</h2>



<h3>REFERENCES</h3>



<p>[Gel] The Gel Programming Language, at
http://gel2.googlecode.com/svn/trunk/doc/gel2_language.html .</p>



<p>[Hejlsberg, 2004] Anders Hejlsberg, Scott Wiltamuth and Peter
Golde.&nbsp; <i>
The C# Programming Language</i>.&nbsp; Addison-Wesley, 2004.</p>



<p>[Henglein, 2005] Fritz Henglein, Henning Makholm, and Henning
Niss.&nbsp; Effect Types and Region-Based Memory
Management.&nbsp; In Benjamin C. Pierce, editor, <i>Advanced
Topics in Types and Programming Languages</i>, MIT Press, 2005.</p>



<p>[Jones, 1996] Richard Jones and Rafael Lins.&nbsp; <i>Garbage
Collection: Algorithms for Automatic Dynamic Memory Management</i>.&nbsp;
John Wiley &amp; Sons, 1996.</p>



<p>[Pierce, 2002] Benjamin C. Pierce.&nbsp; <i>Types
and Programming Languages</i>.&nbsp; MIT Press, 2002.</p>

<p>Bollella, G., Gosling, J., Brosgol, B. M., Dibble, P., Furr, S., Hardin, D., and Turnbull,
M. The Real-Time Specification for Java. The Java Series. Addison-Wesley, 2000.</p>

<p>Chandrasekhar Boyapati, Alexandru Salcianu, William S. Beebee, Martin
C. Rinard: Ownership types for safe region-based memory management in real-time
Java. PLDI 2003: 324-337</p>

<p>Chandrasekhar Boyapati, Barbara Liskov, Liuba Shrira: Ownership types for
object encapsulation. POPL 2003: 213-223 </p>

<p>Michael W. Hicks, J. Gregory Morrisett, Dan Grossman, Trevor Jim: Experience
with safe manual memory-management in cyclone. ISMM 2004: 73-84</p>

<p>Greg Morrisett, Personal communication, 2005.</p>

<p>John Boyland: Alias burying: Unique variables without destructive
reads. Softw., Pract. Exper. 31(6): 533-553 (2001)</p>

<p>Tian Zhao, James Noble, Jan Vitek: Scoped Types for Real-Time Java. RTSS 2004:
241-251</p>

<p>David F. Bacon, Perry Cheng, V. T. Rajan: A real-time garbage collector with
low overhead and consistent utilization. POPL 2003: 285-298 </p>

<p>Roger Henriksson: Scheduling Garbage Collection in Embedded Systems. 
Ph.D. thesis, Lund University, 1998</p>

<p>David G. Clarke, James Noble, John Potter: Simple Ownership Types for Object
Containment. ECOOP 2001: 53-76 



<h2>APPENDIX: SAMPLE PROGRAM</h2>



<p>The following Gel program generates a list of 1,000,000 random
integers, sorts them using a recursive mergesort and then verifies that
the resulting list is in sorted order.</p>



<h3>sort.gel</h3>



<pre>class Random {<br> static int r_ = 1;<br><br> public static int Next() {<br> r_ = r_ * 69069;<br> return r_;<br> }<br>}<br><br>class Node {<br> public readonly int i_;<br> public Node ^next_;<br><br> public Node(int i, Node ^next) { i_ = i; next_ = next; }<br>}<br><br>class Sort {<br> static Node ^RandomList(int count) {<br> Node ^first = null;<br> for (int x = 0 ; x &lt; count ; ++x)<br> first = new Node(Random.Next(), first);<br> return first;<br> }<br><br> static Node ^Merge(Node ^a, Node ^b) {<br> Node ^head = null;<br> Node tail = null;<br> while (a != null &amp;&amp; b != null) {<br> Node ^top;<br> if (a.i_ &lt; b.i_) {<br> top = a;<br> a = take top.next_;<br> } else {<br> top = b;<br> b = take top.next_;<br> }<br> if (head == null) {<br> head = top;<br> tail = head;<br> } else {<br> tail.next_ = top;<br> tail = tail.next_;<br> }<br> }<br> Node ^rest = (a == null) ? b : a;<br> if (tail == null)<br> return rest;<br> tail.next_ = rest;<br> return head;<br> }<br><br> static Node ^MergeSort(Node ^a) {<br> if (a == null || a.next_ == null) return a;<br> Node c = a;<br> Node b = c.next_;<br> while (b != null &amp;&amp; b.next_ != null) {<br> c = c.next_;<br> b = b.next_.next_;<br> }<br> Node ^d = take c.next_;<br> return Merge(MergeSort(a), MergeSort(d));<br> }<br><br> public static void Main(String[] args) {<br> Node ^n = RandomList(1000000);<br> n = MergeSort(n);<br><br> while (n != null) {<br> Node next = n.next_;<br> if (next != null &amp;&amp; n.i_ &gt; next.i_) {<br> Console.WriteLine("failed");<br> return;<br> }<br> n = take n.next_;<br> }<br> Console.WriteLine("succeeded");<br> }<br>}<br></pre>



</body>
</html>
